/*
 * @lc app=leetcode.cn id=304 lang=java
 *
 * [304] 二维区域和检索 - 矩阵不可变
 */

// @lc code=start

class NumMatrix {
    // 这个和昨天的题差不多诶，为了避免重复调用sumRegion的消耗，提前计算一遍
    // 为啥标签有dp啊，虽然说有点像
    // 在外圈加一圈0会好很多，但我一时不知道怎么加，我想到了，把sum数组的长宽多开一个即可
    private int[][] sum;
    public NumMatrix(int[][] matrix) {
        int len1 = matrix.length;
        if(len1 == 0) return;
        int len2 = matrix[0].length;
        this.sum = new int[len1+1][len2+1];
        for(int i = 1 ;i<len1+1;i++){
            for(int j=1;j<len2+1;j++){
                //只要数组开大一个就很方便，少很多判断
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+matrix[i-1][j-1];
            }
        }
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        //由于sum数组多开了一个，行列需要+1才是要求的位置，这样就简单多了
        return sum[row2+1][col2+1]-sum[row2+1][col1]-sum[row1][col2+1]+sum[row1][col1];
    }
}


/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
// @lc code=end

